'''
https://leetcode.cn/problems/range-addition/
'''

from typing import List


class SegmentTree:
    '''
    下标1开始
    '''
    def __init__(self, size):
        self.N = size
        self.info = [0] * (size << 2)
        self.lazy_add = [0] * (size << 2)

    def up(self, root):
        self.info[root] = self.info[root << 1] + self.info[root << 1 | 1]

    def down(self, l, r, root):
        if self.lazy_add[root]:
            m = l + r >> 1
            self.lazy(l, m, root << 1, self.lazy_add[root])
            self.lazy(m+1, r, root << 1 | 1, self.lazy_add[root])
            self.lazy_add[root] = 0

    def lazy(self, l, r, root, v):
        self.lazy_add[root] += v
        self.info[root] += (r-l+1) * v

    def add(self, L, R, V):
        def f(l, r, root):
            if r < L or l > R: return
            if L <= l and r <= R:
                self.lazy(l, r, root, V)
                return
            self.down(l, r, root)
            m = l + r >> 1
            f(l, m, root << 1)
            f(m+1, r, root << 1 | 1)
            self.up(root)
        f(1, self.N, 1)

    def query(self, L, R):
        def f(l, r, root):
            if r < L or l > R: return 0
            if L <= l and r <= R:
                return self.info[root]
            self.down(l, r, root)
            m = l + r >> 1
            return f(l, m, root << 1) + f(m+1, r, root << 1 | 1)
        return f(1, self.N, 1)
            
class DifferenceArray:
    '''
    下标0开始
    '''
    def __init__(self, size):
        self.info = [0] * (size + 1)
        self.size = size
    def add(self, l, r, v):
        self.info[l] += v
        self.info[r+1] -= v
    def get_arr(self):
        info = self.info
        res = [0] * self.size
        res[0] = self.info[0]
        for i in range(1, self.size):
            res[i] = res[i-1] + info[i]
        return res


class Solution:
    # 线段树
    def getModifiedArray(self, length: int, updates: List[List[int]]) -> List[int]:
        tree = SegmentTree(length)
        for L, R, V in updates:
            tree.add(L+1, R+1, V)
        res = [0] * length
        for i in range(length):
            res[i] = tree.query(i+1, i+1)
        return res
    # 差分数组
    def getModifiedArray2(self, length: int, updates: List[List[int]]) -> List[int]:
        tree = DifferenceArray(length)
        for L, R, V in updates:
            tree.add(L, R, V)
        return tree.get_arr()